﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Topcoder
{
    namespace SRM548
    {
        class KingdomAndDucks
        {
            public static int minDucks(int[] duckTypes)
            {
                Dictionary<int, int> duck = new Dictionary<int, int>();
                for (int i = 0; i < duckTypes.Length; i++)
                { 
                    if (duck.ContainsKey(duckTypes[i])) duck[duckTypes[i]]++;
                    else 
                    {
                        duck.Add(duckTypes[i],1);
                    }
                }
                int max = 0;
                foreach (KeyValuePair<int, int> t in duck)
                { 
                    if (t.Value >max) max = t.Value;
                }
                return max * duck.Count;
            }
            
        }
        class KingdomAndTrees
        {
            public static int minLevel(int[] heights)
            {
                int min = 0;
                int minvalue = int.MaxValue;
                int maxvalue = 0;

                for (int i = 0; i < heights.Length; i++)
                {
                    if (heights[i] > maxvalue) maxvalue = heights[i];
                    if (heights[i] < minvalue) minvalue = heights[i];
                }                
                

                while (check(heights) == false)
                {
                    for (int i = 0; i < heights.Length - 1; i++)
                    {
                        if (heights[i] >= heights[i + 1])
                        {
                            int sum = heights[i] + heights[i + 1];
                            if (i != 0)
                            {
                                if (sum / 2 <= heights[i - 1]) sum = heights[i - 1] * 2 + 2;
                            }
                            int level = Math.Max(heights[i] - sum / 2, sum / 2 + 1 - heights[i + 1]);
                            heights[i] = sum / 2;
                            heights[i + 1] = sum / 2 + 1;
                            if (level > min) min = level;
                            break;
                        }
                    }
                }
                return min;
            }
            public static int Try(int[] heights, int add)
            {
                if (heights.Length == 1)
                {
                    int sum = heights[0] + add;
                    int level = Math.Max(heights[0] - sum / 2, sum / 2 + 1 - add);
                    return level;
                }
                else
                { 
                    
                }
            }
            public static bool check(int[] s)
            {
                for (int i = 0; i < s.Length - 1;i++ ) if (s[i] >= s[i + 1]) return false;
                return true;
            }
        }
    }
}
